package com.lei;

import org.junit.Test;
import utilClass.ListNode;

import java.util.*;

public class Work {

    @Test
    // 第2题 两数相加  通过
    public void addTwoNumbers() {
        ListNode node1 = getListNode(3, 4, 2);  // 2 4 3
        ListNode node2 = getListNode(4, 6, 5);  // 5 8

        int s1, s2, s, a = 0, b = 0;
        int[] result;
        ListNode temp = null;
        ArrayList<Integer> list = new ArrayList<Integer>();
        while (true) {
            if (node1 == null && node2 == null) {
                if (a == 1) {
                    list.add(1);
                }
                break;
            } else {
                if (node1 != null) {
                    s1 = node1.val;
                    node1 = node1.next;
                } else {
                    s1 = 0;
                }
                if (node2 != null) {
                    s2 = node2.val;
                    node2 = node2.next;
                } else {
                    s2 = 0;
                }

                s = s1 + s2 + a;
                a = 0;

                if (s > 9) {
                    a = 1;
                    s -= 10;
                }
                //if (temp==null){
                //    temp = new ListNode(s);
                //}else {
                //    ListNode listNode = new ListNode(s);
                //    temp.next = listNode;
                //}
                list.add(s);
            }


        }

        for (int i = 0; i < list.size(); i++) {
            if (temp == null) {
                temp = new ListNode(list.get(list.size() - i - 1));
            } else {
                temp = new ListNode(list.get(list.size() - i - 1), temp);
            }
        }

        System.out.println(temp);
    }


    @Test
    // 第2题 两数相加  通过
    public void addTwoNumbers2() {
        ListNode node1 = getListNode(3, 4, 2);  // 2 4 3
        ListNode node2 = getListNode(4, 6, 5);  // 5 8

        int s1, s2, s = 0;
        ListNode head = new ListNode(-1); //头指针
        ListNode tail = head;  // 尾指针
        while (true) {
            if (node1 == null && node2 == null) {
                if (s > 9) {
                    tail.next = new ListNode(1);
                    tail = tail.next;
                }
                break;
            } else {
                if (node1 != null) {
                    s1 = node1.val;
                    node1 = node1.next;
                } else {
                    s1 = 0;
                }
                if (node2 != null) {
                    s2 = node2.val;
                    node2 = node2.next;
                } else {
                    s2 = 0;
                }
                // 如果 s >=10 有进位 , s/10 =1
                s = s1 + s2 + s / 10;

                tail.next = new ListNode(s % 10);
                tail = tail.next;
            }


        }


        System.out.println(head);
    }


    @Test
    public void testint() {
        String ll1 = "9";
        String ll2 = "1999999999";
        char[] chars1 = ll1.toCharArray();
        for (int i = 0; i < chars1.length / 2; i++) {
            char temp = chars1[i];
            chars1[i] = chars1[chars1.length - i - 1];
            chars1[chars1.length - i - 1] = temp;
        }
        String s1 = new String(chars1);
        char[] chars2 = ll2.toCharArray();
        for (int i = 0; i < chars2.length / 2; i++) {
            char temp = chars2[i];
            chars2[i] = chars2[chars2.length - i - 1];
            chars2[chars2.length - i - 1] = temp;
        }
        String s2 = new String(chars2);

        System.out.println(s1); //9
        System.out.println(s2); //9999999991

        //String s = "" + (Integer.parseInt(s1) + Integer.parseInt(s2));
        //System.out.println(Integer.parseInt(s1));
        //System.out.println(Integer.parseInt(s2));
    }

    @Test
    // 3. 找出其中不含有重复字符的 最长子串 的长度
    public void lengthOfLongestSubstring() {
        String s = "abcabcbb";

        int[] position = new int[128];  // 用于记录字符出现的位置
        for (int i = 0; i < position.length; i++) {
            position[i] = -1;
        }

        int len = 0, max = 0, temp, start = 0;
        for (int i = 0; i < s.length(); i++) {

            Integer c = (int) s.charAt(i);
            if (position[c] == i || position[c] == -1 || position[c] < start) {
                // 该字符在该子串中第一次出现
                position[c] = i;
                len++;
            } else {
                // 该字符重复出现了
                max = Math.max(max, len); // 最长不重复子串的长度

                start = position[c] + 1; // 记录子串头位置
                position[c] = i;  // 记录最近一次字符出现的位置
                i = start - 1;  // 从上一个重复的位置开始
                len = 0;

            }
        }
        max = Math.max(max, len);
        System.out.println(max);
    }

    @Test
    public void findMedianSortedArrays() {
        int[] nums1 = {1, 2};
        int[] nums2 = {3, 4};

        int m = nums1.length;
        int n = nums2.length;
        int len = m + n;
        int[] newArray = new int[len];  // 新的数组
        int i = 0, j = 0; //记录原数组被放入新数组的个数

        for (int k = 0; k < len; k++) {
            if (i == m) {
                // 数组1 已经没有数字了
                newArray[k] = nums2[j++];
            } else if (j == n) {
                newArray[k] = nums1[i++];
            } else if (nums1[i] <= nums2[j]) {
                newArray[k] = nums1[i++];
            } else {
                newArray[k] = nums2[j++];
            }
        }

        if (len % 2 == 0) {
            System.out.println((newArray[len / 2 - 1] + newArray[len / 2]) / 2.0);  // double 变量须除以 2.0
        } else {
            System.out.println(newArray[len / 2]);
        }


    }


    // 第5题 最长回文子串  通过
    @Test
    public static String longestPalindrome(String s) {


        int start = 0;
        int head, tail;
        int index1 = 0, index2 = 0, len = 0;
        while (start < s.length()) {
            int c = s.charAt(start);  // 本次子串的第一个字符

            for (int i = s.length() - 1; i > start; i--) {
                if (s.charAt(i) == c) {
                    // 找到了一个字符相同的字符
                    //String child = s.substring(start + 1, i);// 截取中间字符串

                    // 循环中间串
                    head = start + 1;
                    tail = i - 1;

                    while (head <= tail) {
                        if (!(s.charAt(head) == s.charAt(tail))) {
                            break;
                        }
                        head++;
                        tail--;
                    }
                    if (head > tail) {
                        // 这是一个子串
                        if (len < i - start + 1) {
                            index1 = start;
                            index2 = i;
                            len = i - start + 1;
                        }
                        break; // 跳出循环
                    } else {
                        // 这不是一个子串, 继续循环
                    }
                }
            }

            start++;


        }


        return s.substring(index1, index2 + 1);
    }


    //第8题 字符串转换正数
    @Test
    public static int myAtoi(String s) {
        String a = s.trim();
        if ("".equals(a)) {
            return 0;
        }
        int sign = 1;
        char[] chars = new char[11];  // 2147483647 -2147483648
        int charLength = 0;
        int i = 0;
        char c = a.charAt(i++);

        if (c == '+') {
            sign = 1;
        } else if ('-' == c) {
            sign = -1;
        } else if ('0' == c) {

        } else if ('1' <= c && '9' >= c) {
            chars[charLength++] = c;
        } else {
            return 0;
        }

        for (; i < a.length(); i++) {
            c = a.charAt(i);

            if ('0' == c) {
                if (chars[0] != '\u0000') {
                    chars[charLength++] = c;
                }
            } else if ('1' <= c && '9' >= c) {
                chars[charLength++] = c;
            } else {
                break;
            }

            if (charLength == 11) {
                break;
            }


        }
        if (chars[0] == '\u0000') {
            return 0;
        }
        String trim = new String(chars).trim();

        long result = Long.parseLong(trim) * sign;
        if (result > Integer.MAX_VALUE) {
            return Integer.MAX_VALUE;
        }

        if (result < Integer.MIN_VALUE) {
            return Integer.MIN_VALUE;
        }
        return (int) result;
    }

    // 第6题 Z字形变换
    @Test
    public static void convert() {
        String s = "ABCD";
        int numRows = 3;
        int n = 2 * numRows - 2; // 每一列中间隔了多少个数
        int length = s.length();
        char[] chars = new char[length];
        int charLength = 0;

        if (length < numRows) {
            return;
        }

        for (int i = 0; i < numRows; i++) {
            chars[charLength++] = s.charAt(i);
            for (int j = n; j < length + numRows; j += n) {  // 补齐一个完整的Z字
                if (i == 0) {
                    // 第一行
                    if (j < length) {
                        chars[charLength++] = s.charAt(j);
                    }

                } else if (i == numRows - 1) {
                    // 最后一行
                    if ((j + i) < length) {
                        chars[charLength++] = s.charAt(j + i);
                    }

                } else {
                    // 后面的行数
                    if ((j - i) < length) {
                        chars[charLength++] = s.charAt(j - i);
                    }

                    if (!((j + i) >= length)) {
                        chars[charLength++] = s.charAt(j + i);
                    }
                }
            }
        }

        System.out.println(new String(chars));


    }

    // 第9题 回文数 使用字符串
    public static boolean isPalindrome(int x) {
        String s = "" + x;
        int length = s.length();
        for (int i = 0; i < length / 2; i++) {
            if (s.charAt(i) != s.charAt(length - i - 1)) {
                return false;
            }
        }
        return true;
    }

    // 第9题 回文数 进阶
    public static boolean isPalindrome2(int x) {
        if (x < 0) {
            // 负数不是
            return false;
        }

        if (x < 10) {
            // 一位数 是
            return true;
        }

        int[] ints = new int[10];
        int count = 0;
        while (true) {

            int n = (int) (x / Math.pow(10, count));  //n位数
            if (n == 0) {
                break;
            }
            ints[count++] = n % 10;
        }


        for (int i = 0; i < count / 2; i++) {
            if (ints[i] != ints[count - i - 1]) {
                return false;
            }
        }

        return true;
    }


    // 第9题 回文数 进阶2
    public static boolean isPalindrome3(int x) {
        if (x < 0) {
            // 负数不是
            return false;
        }
        int n = x;

        int result = 0;  // 计算出x的倒序值 , 判断是否与x相等

        while (n != 0) {
            result = result * 10 + n % 10;
            n = n / 10;
        }

        return result == x;
    }

    // 第10题 难
    public static boolean isMatch(String s, String p) {
        for (int i = 0; i < p.length(); i++) {
            char c = p.charAt(i);
        }
        return true;
    }

    // 第11题 盛最多水的容器
    public int maxArea(int[] height) {

        int max = 0;
        for (int i = 0; i < height.length; i++) {
            for (int j = i; j < height.length; j++) {
                if ((j - i) * Math.min(height[i], height[j]) > max) {
                    max = (j - i) * Math.min(height[i], height[j]);
                }
            }
        }

        return max;
    }

    // 第11题 盛最多水的容器 进阶
    public static int maxArea2(int[] height) {
        int left = 0;
        int right = height.length - 1;
        int max = 0;

        while (left < right) {
            if (height[left] < height[right]) {
                max = Math.max((right - left) * height[left++], max);
            } else {
                max = Math.max((right - left) * height[right--], max);
            }
        }


        return max;
    }

    // 第12题 整数转罗马数字
    public static String intToRoman(int num) {
        String result = "";

        while (num > 0) {
            if (num >= 1000) {
                do {
                    result += "M";
                    num -= 1000;
                } while (num >= 1000);
            } else if (num >= 900) {
                result += "CM";
                num -= 900;
            } else if (num >= 500) {
                result += "D";
                num -= 500;
            } else if (num >= 400) {
                result += "CD";
                num -= 400;
            } else if (num >= 100) {
                do {
                    result += "C";
                    num -= 100;
                } while (num >= 100);
            } else if (num >= 90) {
                result += "XC";
                num -= 90;
            } else if (num >= 50) {
                result += "L";
                num -= 50;
            } else if (num >= 40) {
                result += "XL";
                num -= 40;
            } else if (num >= 10) {
                do {
                    result += "X";
                    num -= 10;
                } while (num >= 10);
            } else if (num == 9) {
                result += "IX";
                num -= 9;
            } else if (num >= 5) {
                result += "V";
                num -= 5;
            } else if (num == 4) {
                result += "IV";
                num -= 4;
            } else {
                do {
                    result += "I";
                    num -= 1;
                } while (num >= 1);
            }
        }

        return result;
    }

    // 第12题 整数转罗马数字 进阶1
    public static String intToRoman1(int num) {

        String result = "";

        int m = num / 1000;
        num = num % 1000;
        for (int i = 0; i < m; i++) {
            result += "M";
        }

        if (num >= 900) {
            num -= 900;
            result += "CM";
        }

        if (num >= 500) {
            num -= 500;
            result += "D";
        }

        if (num >= 400) {
            num -= 400;
            result += "CD";
        }

        int c = num / 100;
        num = num % 100;
        for (int i = 0; i < c; i++) {
            result += "C";
        }

        if (num >= 90) {
            num -= 90;
            result += "XC";
        }

        if (num >= 50) {
            num -= 50;
            result += "L";
        }

        if (num >= 40) {
            num -= 40;
            result += "XL";
        }

        int x = num / 10;
        num = num % 10;
        for (int i = 0; i < x; i++) {
            result += "X";
        }

        if (num == 9) {
            result += "IX";
        } else {
            if (num >= 5) {
                result += "V";
                num -= 5;

                for (int i = 0; i < num; i++) {
                    result += "I";
                }
            } else if (num == 4) {
                result += "IV";
            } else {
                for (int i = 0; i < num; i++) {
                    result += "I";
                }
            }
        }


        return result;

    }

    // 第12题 整数转罗马数字 进阶2
    public static String intToRoman2(int num) {
        String result = "";
        int[] ints = new int[]{1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
        String[] strings = new String[]{"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};

        /***
         * 第一种解法
         */
        //for (int i = 0; i < ints.length; i++) {
        //    int count = num / ints[i];
        //    num = num%ints[i];
        //    for (int j = 0; j < count; j++) {
        //        result+=strings[i];
        //    }
        //}

        /**
         * 第二种解法
         */
        int index = 0;
        while (index < 13) {
            if (num >= ints[index]) {
                num -= ints[index];
                result += strings[index];
            } else {
                index++;
            }
        }
        return result;
    }

    // 第12题 整数转罗马数字 进阶3
    public static String intToRoman3(int num) {
        String result = "";
        int[] ints = new int[]{3000, 2000, 1000, 900, 500, 400, 300, 200, 100
                , 90, 50, 40, 30, 20, 10, 9, 5, 4, 3, 2, 1};
        String[] strings = new String[]{"MMM", "MM", "M", "CM", "D", "CD", "CCC", "CC", "C",
                "XC", "L", "XL", "XXX", "XX", "X", "IX", "V", "IV", "III", "II", "I"};

        for (int i = 0; i < ints.length; i++) {
            if (num >= ints[i]) {
                result += strings[i];
                num -= ints[i];
            }
        }
        return result;
    }

    // 第13题 罗马转换成数字
    public static int romanToInt(String s) {
        char[] chars = s.toCharArray();
        int sum = 0;
        int i = 0;

        for (; i < chars.length - 1; i++) {
            char roman = chars[i];
            if (roman == 'I') {
                if (chars[i + 1] == 'V' || chars[i + 1] == 'X') {
                    if (chars[i + 1] == 'V') {
                        sum += 4;
                    } else {
                        sum += 9;
                    }
                    i++;
                } else {
                    sum += 1;
                }
            } else if (roman == 'X') {
                if (chars[i + 1] == 'L' || chars[i + 1] == 'C') {
                    if (chars[i + 1] == 'L') {
                        sum += 40;
                    } else {
                        sum += 90;
                    }
                    i++;
                } else {
                    sum += 10;
                }
            } else if (roman == 'C') {
                if (chars[i + 1] == 'D' || chars[i + 1] == 'M') {
                    if (chars[i + 1] == 'D') {
                        sum += 400;
                    } else {
                        sum += 900;
                    }
                    i++;
                } else {
                    sum += 100;
                }
            } else {
                if (roman == 'V') {
                    sum += 5;
                }
                if (roman == 'L') {
                    sum += 50;
                }
                if (roman == 'D') {
                    sum += 500;
                }
                if (roman == 'M') {
                    sum += 1000;
                }
            }
        }
        if (i + 1 == chars.length) {
            if (chars[i] == 'I') {
                sum += 1;
            }
            if (chars[i] == 'V') {
                sum += 5;
            }
            if (chars[i] == 'X') {
                sum += 10;
            }
            if (chars[i] == 'L') {
                sum += 50;
            }
            if (chars[i] == 'C') {
                sum += 100;
            }
            if (chars[i] == 'D') {
                sum += 500;
            }
            if (chars[i] == 'M') {
                sum += 1000;
            }


        }


        return sum;
    }

    // 第13题 罗马转换成数字 简短版
    public static int romanToInt2(String s) {
        s = s.replaceAll("IV", "a");
        s = s.replaceAll("IX", "b");
        s = s.replaceAll("XL", "c");
        s = s.replaceAll("XC", "d");
        s = s.replaceAll("CD", "e");
        s = s.replaceAll("CM", "f");

        int result = 0;
        for (int i = 0; i < s.length(); i++) {
            result += getValue(s.charAt(i));
        }
        return result;
    }

    public static int getValue(char roman) {
        switch (roman) {
            case 'I':
                return 1;
            case 'V':
                return 5;
            case 'X':
                return 10;
            case 'L':
                return 50;
            case 'C':
                return 100;
            case 'D':
                return 500;
            case 'M':
                return 1000;
            case 'a':
                return 4;
            case 'b':
                return 9;
            case 'c':
                return 40;
            case 'd':
                return 90;
            case 'e':
                return 400;
            case 'f':
                return 900;
        }
        return 0;
    }

    public static String longestCommonPrefix(String[] strs) {
        String result = "";
        boolean flag = true;
        char a;
        if (strs.length == 0 || strs[0] == "") {
            return result;
        }
        while (flag == true) {
            for (int j = 0; j < 200; j++) {
                a = strs[0].charAt(j);
                for (int i = 1; i < strs.length; i++) {
                    if (j == strs[i].length() || strs[i].charAt(j) != a) {
                        // 判断到此为止
                        flag = false;
                        break;
                    }
                }
                if (flag == false) {
                    break;
                }
                result += a;
            }
        }
        return result;
    }

    // 第15题 三数之和
    public static List<List<Integer>> threeSum(int[] nums) {
        ArrayList<List<Integer>> result = new ArrayList<>();
        Arrays.sort(nums);

        for (int i = 0; i < nums.length; i++) {
            int a = nums[i];
            if (a > 0) {
                return result;
            }
            if (i > 0 && a == nums[i - 1]) {
                continue;
            }
            int left = i + 1;
            int right = nums.length - 1;
            while (left < right) {
                int sum = a + nums[left] + nums[right];
                if (sum == 0) {
                    ArrayList<Integer> integers = new ArrayList<>();
                    integers.add(a);
                    integers.add(nums[left]);
                    integers.add(nums[right]);
                    result.add(integers);
                    if (nums[left] == nums[right]) {
                        break;
                    }
                    left++;
                    right--;
                    while (nums[left] == nums[left - 1]) {
                        left++;
                    }
                    while (nums[right] == nums[right + 1]) {
                        right--;
                    }
                } else if (sum < 0) {
                    left++;
                } else {
                    right--;
                }
            }
        }


        return result;
    }

    //第20题 ， 有效的括号 shit , 为啥 中括号可以在小括号里面
    public static boolean isValid(String s) {
        s = s.replaceAll("\\(\\)", "");  // ()小括号一定是在一起的，否则就是false， 所以在一起的小括号不需要进行判断
        s = s.replaceAll("\\[\\]", "");  // 中括号也应该是一起的了
        s = s.replaceAll("\\{\\}", "");

        if ("".equals(s)) {
            return true;
        }
        return false;
    }

    // 第20题进阶
    public static boolean isValid2(String s) {
        //if (s.length()%2==1){
        //    return false;
        //}
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == '(' || c == '[' || c == '{') {
                stack.push(c);
            } else if (!stack.empty() && (stack.peek() == (c - 2) || stack.peek() == (c - 1))) {
                stack.pop();
            } else {
                return false;
            }
        }
        return stack.empty();
    }

    // 第21题合并两个有序链表
    public static ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode head = new ListNode();
        ListNode tail = head;

        while (l1 != null && l2 != null) {
            if (l1.val < l2.val) {
                tail.next = new ListNode(l1.val);
                tail = tail.next;
                l1 = l1.next;
            } else {
                tail.next = new ListNode(l2.val);
                tail = tail.next;
                l2 = l2.next;
            }
        }
        if (l1 == null) {
            tail.next = l2;
        }
        if (l2 == null) {
            tail.next = l1;
        }
        return head.next;
    }

    // 第21题合并两个有序链表 递归
    public static ListNode mergeTwoLists2(ListNode l1, ListNode l2) {
        if (l1 == null) {
            return l2;
        }
        if (l2 == null) {
            return l1;
        }
        if (l1.val < l2.val) {
            l1.next = mergeTwoLists2(l1.next, l2);
            return l1;
        } else {
            l2.next = mergeTwoLists2(l1, l2.next);
            return l2;
        }
    }

    // 第26题 删除排序数组中的重复项
    public static int removeDuplicates(int[] nums) {
        // 经提交检验，没有空数组的输入现象
        int head = 0;
        int tail = 0;
        while (tail < nums.length) {
            if (nums[tail++] != nums[head]) {
                nums[++head] = nums[tail - 1];
            }
        }
        return head + 1;
    }

    // 第27题 移除元素
    public int removeElement(int[] nums, int val) {
        int len = nums.length;
        for (int i = 0; i < len; i++) {
            if (nums[i] == val) {
                nums[i--] = nums[--len];
            }
        }
        return len;
    }

    // 第28题 实现strStr() 代码简短版 暴力匹配
    public static int strStr(String haystack, String needle) {
        int head = 0;
        int len = 0;
        while (len < needle.length() && head < haystack.length()) {
            if (haystack.charAt(head++) != needle.charAt(len++)) {
                head -= (len - 1);
                len = 0;
            }
        }
        return len == needle.length() ? head - len : -1;
    }

    // 第28题 实现strStr() 代码简短版 暴力匹配
    public static int strStr2(String haystack, String needle) {

        return 0;
    }

    // 第35题 搜索插入位置
    public static int searchInsert(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return left;
    }

    // 第38题 外观数列 递归
    public static String countAndSay(int n) {
        // 可以把len  改成 start
        if (n == 1) {
            return "1";
        }
        String s = countAndSay(n - 1);
        //String s = "21";
        char c = s.charAt(0);
        int len = 1;
        String result = "";
        for (int i = 1; i < s.length(); i++) {
            if (c == s.charAt(i)) {
                len++;
            } else {
                result += len + "" + c;
                c = s.charAt(i);
                len = 1;
            }
        }
        return result + len + c;
    }


    // 第38题 外观数列2
    public static String countAndSay2(int n) {
        if (n == 1) {
            return "1";
        }
        String lastResult = "1";
        String result = "";
        for (int i = 0; i < n - 1; i++) {
            result = "";
            char c = lastResult.charAt(0);
            int len = 1;
            for (int j = 1; j < lastResult.length(); j++) {
                if (c == lastResult.charAt(j)) {
                    len++;
                } else {
                    result += len + "" + c;
                    c = lastResult.charAt(j);
                    len = 1;
                }
            }
            result += len + "" + c;
            lastResult = result;
        }
        return result;
    }

    // 第53题 最大子序和
    public static int maxSubArray(int[] nums) {
        int start = -1;
        int end = -1;
        int max = -1000000;
        // 找到第一个正数
        for (int i = 0; i < nums.length; i++) {
            max = Math.max(max, nums[i]);
            if (nums[i] > 0) {
                start = i;
                max = nums[i];
                break;
            }
        }
        if (start == -1) {
            return max;
        }
        int temp = max;
        // 找到第二个正数
        for (int i = start + 1; i < nums.length; i++) {
            temp += nums[i];
            if (nums[i] > 0) {
                if (max <= temp) {
                    max = Math.max(temp, nums[i]);
                }
                temp = Math.max(temp, nums[i]);
            }
        }

        return Math.max(max, temp);
    }

    // 第53题 最大子序和 动态规划
    public static int maxSubArray2(int[] nums) {
        // 定义一个数组，意为以 第n位 数字为末尾的最大和 ， maxSubArray[n] 总是可以由 maxSubArray[n-1]得到
        int[] maxSubArray = new int[nums.length];
        maxSubArray[0] = nums[0];
        int max = maxSubArray[0];

        for (int i = 1; i < maxSubArray.length; i++) {
            maxSubArray[i] = Math.max(maxSubArray[i - 1] + nums[i], nums[i]);
            max = Math.max(max, maxSubArray[i]);
        }

        return max;
    }

    // 第58题， 最后一个单词的长度
    public int lengthOfLastWord(String s) {
        s = s.trim();
        int i = s.lastIndexOf(" ");
        return s.substring(i + 1).length();
    }

    // 第66题 ， 加一
    public int[] plusOne(int[] digits) {
        int i = digits.length - 1;
        for (; i >= 0; i--) {
            if (digits[i] != 9) {
                digits[i] = digits[i] + 1;
                return digits;
            }
            digits[i] = 0;
        }

        int[] ints = new int[digits.length + 1];
        ints[0] = 1;
        return ints;
    }

    // 第67题 二进制求和
    public String addBinary(String a, String b) {
        int aNeedle = a.length()-1;
        int bNeedle = b.length()-1;
        StringBuilder builder = new StringBuilder();
        int temp = 0;
        while (true){
            temp = (a.charAt(aNeedle)-48) + (b.charAt(bNeedle)-48) + temp;

            builder.append(aNeedle);
        }


    }


    public static void main(String[] args) {
        System.out.println((int) '0');  //48
        System.out.println((int) '1');  //49

    }


    /**
     * 有n个阶梯，1次能走k步，总共有多少种方法  递归
     *
     * @param n 目标层数
     * @param k 1次能走多少步
     * @return
     */
    public static long nLadderkStep(int n, int k) {
        if (n <= k) {
            return (long) Math.pow(2, n - 1);
        }
        int sum = 0;
        for (int i = 1; i <= k; i++) {
            sum += nLadderkStep(n - i, k);
        }
        return sum;
    }

    public static long nLadderkStep2(int n, int k) {
        if (n <= k) {
            return (long) Math.pow(2, n - 1);
        }
        long[] step = new long[k + 1];
        int m = k;
        for (int i = 1; i <= k; i++) {
            step[i] = (int) Math.pow(2, --m);  // 初始化最后要走k步的步数
        }
        long sum = 0;
        for (int i = k + 1; i <= n; i++) {
            sum = 0;
            for (int j = k; j >= 1; j--) {
                sum += step[j];
                step[j] = step[j - 1];
            }
            step[1] = sum;
        }
        return sum;
    }

    // 取模运算, 解决存不下的问题
    public static int nLadderkStep3(int n, int k) {
        if (n <= k) {
            return (int) (Math.pow(2, n - 1) % 100003);
        }
        long[] step = new long[k + 1];
        int m = k;
        for (int i = 1; i <= k; i++) {
            step[i] = (int) Math.pow(2, --m) % 100003;  // 初始化最后要走k步的步数
        }
        int sum = 0;
        for (int i = k + 1; i <= n; i++) {
            sum = 0;
            for (int j = k; j >= 1; j--) {
                sum += step[j];
                step[j] = step[j - 1];
            }
            step[1] = sum % 100003;
        }
        return sum % 100003;
    }


    @Test
    public void b() {
        System.out.println(Long.parseLong("1000000000000000000000000000001"));
    }


    public ListNode getListNode(int... a) {
        ListNode temp = null;
        for (int i : a) {
            if (temp == null) {
                temp = new ListNode(i);
            } else {
                temp = new ListNode(i, temp);
            }
        }
        return temp;
    }
}
